/*
Revision History:
Author                          Date          Version     Description of Changes
------------------------------------------------------------------------------------------
Jongwon Seo				 	 2010/02/20 	    1.0				 Created
neryong@gmail.com
*/

#ifndef __BIT_TRIE_H__
#define __BIT_TRIE_H__

#include <stdio.h>
#include <stdlib.h>
#include <vector>

namespace neryong
{

template<int T>
class base_stride_util
{
public:
	enum
	{
		STRIDE = T,
		STRIDE_MASK	= (1<<STRIDE)-1,
	};
	/**
		\brief	extract sub bitmap from index bit to index+STRIDE bit of bitmap
	*/
	static inline	uint8_t	sub_bitmap(uint8_t* bitmap,uint32_t index)
	{
		return (bitmap[index>>3]>>(8-STRIDE-index%8))&STRIDE_MASK;
	}
};

/**
	\brief 	special class for STRIDE size is 8
*/
class base_stride_util_8
{
public:
	enum
	{
		STRIDE = 8,
		STRIDE_MASK	= (1<<STRIDE)-1,
	};
	static inline	uint8_t	sub_bitmap(uint8_t* bitmap,uint32_t index)
	{
		return bitmap[index>>3];
	}
};

template<int WINDOW,class ALLOCATOR=std::allocator<char> >
class bit_trie_node
{
public:
	void* operator new(size_t size)
	{	ALLOCATOR a;
		return a.allocate(size);
	}
	void operator delete(void* p)
	{	ALLOCATOR a;
		a.deallocate((char*)p,sizeof(bit_trie_node));
	}
	bit_trie_node(bit_trie_node* parent)
	{	_parent = parent;
		memset(_child,0,sizeof(_child));
	}
	virtual ~bit_trie_node()
	{
	}
	void	release()
	{	for ( int i = 0 ; i < WINDOW ; i++ )
		{	if ( _child[i] )
			{	_child[i]->_parent = NULL;
				_child[i]->release();
			}
		}
		if ( _parent )
		{	for ( int i = 0 ; i < WINDOW ; i++ )
			{	if ( _parent->_child[i] == this )
					_parent->_child[i] = NULL;
			}
		}
		delete this;
	}
	void	move_children_to(bit_trie_node& r)
	{	memmove(r._child,_child,sizeof(_child));
		memset(_child,0,sizeof(_child));
		for ( int i = 0 ; i < WINDOW ; i++ )
		{	if ( r._child[i] )
			{	r._child[i]->_parent = &r;
			}
		}
	}
	bit_trie_node*		_parent;
	bit_trie_node*		_child[WINDOW];
};

template<int SIZE,class DATA,class STRIDE_UTIL,class ALLOCATOR=std::allocator<char> >
class base_bit_trie
{
public:
};

/**
	\class	bit trie template class
	\param	SIZE		byte count of key
	\param	DATA		data type
	\param	STRIDE_UTIL	class defines stdride size and utitly 
*/
template<int SIZE,class DATA,class STRIDE_UTIL,class ALLOCATOR=std::allocator<char> >
class bit_trie : public base_bit_trie<SIZE,DATA,STRIDE_UTIL,ALLOCATOR>
{
protected:
	enum
	{	STRIDE		= STRIDE_UTIL::STRIDE,
		WINDOW 		= 1<<STRIDE,
		BITLEN 		= SIZE*8,
	};
	class node : public bit_trie_node<WINDOW,ALLOCATOR>
	{
	public:
		node(node* parent) : bit_trie_node<WINDOW,ALLOCATOR>(parent)
		{	_is_leaf = false;
		}
		static inline node* create(node* parent)
		{	return new node(parent);
		}
		inline	bool	is_empty()
		{
			if ( _is_leaf )
				return false;
			for ( int i = 0 ; i < WINDOW ; i++ )
			{	node* p = (node*)bit_trie_node<WINDOW,ALLOCATOR>::_child[i];
				if ( p && p->is_empty() )
					return false;
			}
			return true;
		}
		bool			_is_leaf;
	};
	class leaf : public node
	{
	public:
		void* operator new(size_t size)
		{	ALLOCATOR a;
			return a.allocate(size);
		}
		void operator delete(void* p)
		{	ALLOCATOR a;
			a.deallocate((char*)p,sizeof(leaf));
		}
		static inline leaf* create(node* parent)
		{	return new leaf(parent);
		}
		leaf(node* parent) : node(parent)
		{	node::_is_leaf = true;
		}
		DATA	_data;
	};
public:	
	enum
	{
		NODE_SIZE	= sizeof(node),
		LEAF_SIZE	= sizeof(leaf),
	};
	bit_trie()
	{	_root = node::create(NULL);
	}
	~bit_trie()
	{	_root->release();
	}
	inline	void	clear()
	{	delete _root;
		_root = node::create(NULL);
	}
	inline	bool	insert(uint8_t* bitmap,uint32_t mask_len,const DATA& data)
	{
		bool is_new_leaf = true;
		uint32_t index = 0;
		node* current_node = _root;
		while ( true )
		{
			uint8_t i = STRIDE_UTIL::sub_bitmap(bitmap,index);
			if ( index + STRIDE < mask_len )
			{
				node* next_node = (node*)current_node->_child[i];
				if ( !next_node )
				{	next_node = node::create(current_node);
					current_node->_child[i] = next_node;
				}
				current_node = next_node;
				index += STRIDE;
			}
			else
			{	uint8_t begin = i & ( 0xff << (index+STRIDE-mask_len) );
				uint8_t end = begin + (1<<(index + STRIDE-mask_len)) - 1;
				for ( int slot = begin ; slot <= end ; slot++ )
				{	leaf* new_leaf = leaf::create(current_node);
					new_leaf->_is_leaf = true;
					new_leaf->_data = data;
					node* old_node = (node*)current_node->_child[slot];
					if ( old_node )
					{	old_node->move_children_to(*new_leaf);
						old_node->release();
						is_new_leaf = false;
					}
					current_node->_child[slot] = new_leaf;
				}
				break;
			}
		}
		return is_new_leaf;
	}
	inline	void	erase(uint8_t* bitmap,uint32_t mask_len,const DATA& data)
	{	
		uint32_t index = 0;
		node* current_node = _root;
		while ( true )
		{
			uint8_t i = STRIDE_UTIL::sub_bitmap(bitmap,index);
			if ( index + STRIDE < mask_len )
			{
				node* next_node = current_node->_child[i];
				if ( !next_node )
				{	break;
				}
				current_node = next_node;
				index += STRIDE;
			}
			else
			{	uint8_t begin = i & ( 0xff << (index+STRIDE-mask_len) );
				uint8_t end = begin + (1<<(index + STRIDE-mask_len)) - 1;
				for ( int slot = begin ; slot <= end ; slot++ )
				{	node* target_node = (node*)current_node->_child[slot];
					if ( target_node && target_node->_is_leaf && target_node->data == data )
					{	
						target_node->_is_leaf = false;
						if ( target_node->is_empty() )
						{	target_node->release();
						}
						else
						{	node* new_node = node::create(current_node);
							target_node->move_children_to(*new_node);
							target_node->release();
							current_node->_child[slot] = new_node;
						}
					}
				}
				break;
			}
		}
	}
	inline	const DATA*	find(uint8_t* bitmap) const
	{	
		uint32_t index = 0;
		node* current_node = _root;
		while ( current_node )
		{
			if ( current_node->_is_leaf == true )
			{	return &((leaf*)current_node)->_data;
			}
			uint8_t i = STRIDE_UTIL::sub_bitmap(bitmap,index);
			current_node = (node*)current_node->_child[i];
			index += STRIDE;
		}
		return NULL;
	}
protected:
	node*	_root;
};

/**
	\class	bit trie template class. this class supports multi data mapping.
	\param	SIZE		byte count of key
	\param	DATA		data type
	\param	STRIDE_UTIL	class defines stdride size and utitly 
*/
template<int SIZE,class DATA,class STRIDE_UTIL,class ALLOCATOR=std::allocator<char> >
class multi_bit_trie : public base_bit_trie<SIZE,DATA,STRIDE_UTIL,ALLOCATOR>
{
protected:
	enum
	{	STRIDE		= STRIDE_UTIL::STRIDE,
		WINDOW 		= 1<<STRIDE,
		BITLEN 		= SIZE*8,
	};
	class node : public bit_trie_node<WINDOW,ALLOCATOR>
	{
	public:
		node(node* parent) : bit_trie_node<WINDOW,ALLOCATOR>(parent)
		{
		}
		static inline node* create(node* parent)
		{	return new node(parent);
		}
		inline	bool	is_empty()
		{
			if ( _data.size() > 0 )
				return false;
			for ( int i = 0 ; i < WINDOW ; i++ )
			{	node* p = (node*)bit_trie_node<WINDOW,ALLOCATOR>::_child[i];
				if ( p && p->is_empty() )
					return false;
			}
			return true;
		}
		std::vector<DATA>	_data;
	};
	
public:
	enum
	{
		NODE_SIZE	= sizeof(node),
	};
	multi_bit_trie()
	{	_root = node::create(NULL);
	}
	~multi_bit_trie()
	{	_root->release();
	}
	inline	void	clear()
	{	delete _root;
		_root = node::create(NULL);
	}
	inline	void	insert(uint8_t* bitmap,uint32_t mask_len,const DATA& data)
	{
		uint32_t index = 0;
		node* current_node = _root;
		while ( true )
		{
			uint8_t i = STRIDE_UTIL::sub_bitmap(bitmap,index);
			if ( index + STRIDE < mask_len )
			{
				node* next_node = (node*)current_node->_child[i];
				if ( !next_node )
				{	next_node = node::create(current_node);
					current_node->_child[i] = next_node;
				}
				current_node = next_node;
				index += STRIDE;
			}
			else
			{	uint8_t begin = i & ( 0xff << (index+STRIDE-mask_len) );
				uint8_t end = begin + (1<<(index + STRIDE-mask_len)) - 1;
				for ( int slot = begin ; slot <= end ; slot++ )
				{	
					node* target_node = (node*)current_node->_child[slot];
					if ( !target_node )
					{	target_node = node::create(current_node);
						current_node->_child[slot] = target_node;
					}
					target_node->_data.push_back(data);
				}
				break;
			}
		}
	}
	inline	void	erase(uint8_t* bitmap,uint32_t mask_len,const DATA& data)
	{	
		uint32_t index = 0;
		node* current_node = _root;
		while ( true )
		{
			uint8_t i = STRIDE_UTIL::sub_bitmap(bitmap,index);
			if ( index + STRIDE < mask_len )
			{
				node* next_node = (node*)current_node->_child[i];
				if ( !next_node )
				{	break;
				}
				current_node = next_node;
				index += STRIDE;
			}
			else
			{	uint8_t begin = i & ( 0xff << (index+STRIDE-mask_len) );
				uint8_t end = begin + (1<<(index + STRIDE-mask_len)) - 1;
				for ( int slot = begin ; slot <= end ; slot++ )
				{	
					node* target_node = (node*)current_node->_child[slot];
					if ( target_node )
					{	for ( typename std::vector<DATA>::iterator datai = target_node->_data.begin() ; datai != target_node->_data.end() ; datai++ )
						{	if ( *datai == data )
							{	target_node->_data.erase(datai);
								if ( target_node->is_empty() )
									target_node->release();
								break;
							}
						}
					}
				}
				break;
			}
		}
	}
	template<class RESULT>
	inline	void	find(uint8_t* bitmap,RESULT& r) const
	{	
		uint32_t index = 0;
		node* current_node = _root;
		do
		{
			if ( current_node->_data.size() )
			{	r.add(current_node->_data);
			}
			uint8_t i = STRIDE_UTIL::sub_bitmap(bitmap,index);
			current_node = (node*)current_node->_child[i];
			index += STRIDE;
		} while ( current_node );
	}
protected:
	node*	_root;
};

}

#endif //__BIT_TRIE_H__
